class MySingleNode {
    static class ListNode2{
        public int value2;//数据
        public ListNode2 next2;//地址

        public ListNode2(int value2) {
            this.value2 = value2;
        }
    }

    public ListNode2 head2;

    //创建链表2
    public void createNode() {
        ListNode2 listNode5 = new ListNode2(12);
        ListNode2 listNode6 = new ListNode2(23);
        ListNode2 listNode7 = new ListNode2(34);

        listNode5.next2 = listNode6;
        listNode6.next2 = listNode7;

        this.head2 = listNode5;//head2指向第二个链表的头结点
    }
    public void disPlay() {
      ListNode2 cur = this.head2;
        while (cur != null) {
            System.out.print(cur.value2 + " ");
            cur = cur.next2;//cur指向它的下一个
        }
        System.out.println();//换行
    }

}

public class MySingleList {
    static class ListNode {
        public int value;//数据
        public ListNode next;//地址

        public ListNode(int value) {
            this.value = value;
        }
    }

    //创建表头
    public ListNode head;

    //创建链表1
    public void createList() {
        ListNode listNode1 = new ListNode(123);
        ListNode listNode2 = new ListNode(234);
        ListNode listNode3 = new ListNode(345);
        ListNode listNode4 = new ListNode(456);

        //将节点连接起来
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        //将head指向表头
        this.head = listNode1;

    }

    //打印链表
    public void disPlay() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;//cur指向它的下一个
        }
        System.out.println();//换行
    }

    /*
     * NO.2
     * @ 反转链表
     * */
    public ListNode reversalList() {
        //链表为空的情况
        if (this.head == null) {
            return null;
        }

        //一个结点的情况
        if (head.next == null) {
            return head;
        }
        //1.先定义一个cur
        ListNode cur = head.next;

        //2.把head结点置为null
        head.next = null;//这个时候作为头结点的head就与后面的结点断开了

        //3.采用头插法依次将head后面的结点头插到head之前
        //先定义一个curNext始终指向cur.next
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;//cur的地址域指向head的地址 - 这就插到了head之前
            head = cur;//head指向了当前头结点的位置
            cur = curNext;//cur指向它的下一个结点
        }
        return head;
    }

    /*
     * NO.1
     * @ 删除链表中等于给定值Val的所有结点
     * */
    public void removeAllVal(int key) {
        //如果表示空的
        if (this.head == null) {
            return;
        }
        ListNode cur = this.head.next;//cur指向要删除的结点
        ListNode prev = this.head;//指向要删除结点的前一个结点
        while (cur != null) {
            if (cur.value == key) {
                prev.next = cur.next;//prev的地址域指向要删除结点的后一个结点
                cur = cur.next;//指向下一个
            } else {
                prev = cur;
                cur = cur.next;//指向下一个
            }
        }

        //如果第一个结点是key
        if (this.head.value == key) {
            this.head = this.head.next;//直接指向下一个
        }
    }

    /*
     * NO.3
     * @ 返回中间的结点
     * */
    public ListNode middleNode() {
        //1.定义一个fast和slow
        ListNode fast = this.head;
        ListNode slow = this.head;

        //2.fast每次走两步，slow每次走一步
        //判断奇数和偶数个结点
        while (fast != null && fast.next != null) {
            //如果是偶数就返回第二个中间结点
            //如果是奇数就返回中间的结点
            fast = fast.next.next;//走两个
            slow = slow.next;//走一个
        }
        return slow;//此时的slow就是中间的结点
    }

    /*
     * NO.4
     * @ 输出倒数第k个结点
     * */
    public ListNode findKthToTail(int k) {
        //k位置不合法
        if (k <= 0 || this.head == null) {
            return null;
        }

        //定义一个fast和slow指向head
        ListNode fast = this.head;
        ListNode slow = this.head;

        //先让fast走k-1步
        while (k - 1 != 0) {
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            k--;
        }

        //然后两个一起走
        //当fast.next==null的时候，slow所指的位置就是倒数第k个结点
        while (fast.next != null) {
            //两个一起走
            fast = fast.next;
            slow = slow.next;
        }
        return slow;//此时slow指向的就是倒数第k个结点
    }

    //求链表结点个数
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;//结点个数
    }

    /*
     * No.5
     * @ 合并有序链表
     * */
    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;//虚拟结点，不是真是存在的
        while (head1 != null && head2 != null) {
            //说明head1小
            if (head1.value < head2.value) {
                tmp.next = head1;//将tmp指向当前的较小的结点head1
                head1 = head1.next;//让head1指向下一个
            } else { //说明和head2小
                tmp.next = head2;//将tmp指向当前的较小的结点head2
                head2 = head2.next;//让head2指向下一个
            }
            //head1和head2移动后，tmp每次要指向当前的较小结点
            tmp = tmp.next;
        }

        //说明链表1还没有比较完
        if (head1 != null) {
            //tmp要在链表1中指向当前的的较小的结点
            tmp.next = head1;
        }

        //说明链表2还没有比较完
        if (head2 != null) {
            //tmp要在链表2中指向当前的的较小的结点
            tmp.next = head2;
        }
        return newHead.next;//返回的是合并后的头结点
    }

    /*
     * NO.6
     * @ 链表分割
     * */
    public ListNode segmentationList(ListNode head, int x) {
        ListNode cur = this.head;
        ListNode beforeStart = null;//始终指向前面结点的头部
        ListNode beforeEnd = null;//始终指向前面结点的尾部
        ListNode afterStart = null;//始终指向后面结点的头部
        ListNode afterEnd = null;//始终指向后面结点的尾部
        //cur等于null，遍历结束
        while (cur != null) {
            if (cur.value < x) {
                //如果是第一次插入
                if (beforeStart == null) {
                    //都从头开始
                    beforeStart = cur;
                    beforeEnd = cur;
                } else { //不是第一次插入
                    //前面的要往后走
                    beforeEnd.next = cur;//与beforeEnd后面的呢结点相连
                    beforeEnd = beforeEnd.next;//将beforeEnd指向它的下一个结点
                }
            } else {
                if (afterStart == null) {
                    //都从头开始
                    afterStart = cur;
                    afterEnd = cur;
                } else { //不是第一次插入
                    //后面的要往后走
                    afterEnd.next = cur;//与afterEnd后面的呢结点相连
                    afterEnd = afterEnd.next;//将afterEnd指向它的下一个结点
                }
            }
            cur = cur.next;//cur往后走
        }

        //链表中可能没有<x的或者是>=x的，也就是前面或者后面没有数据 - 若此时还将收尾相连则会包空指针异常
        //前面没有数据，数据全在后面
        if (beforeStart == null) {
            return afterStart;//此时afterStart是链表的头结点
        }

        //如果原表的最后一个结点小于x，排列后的链表将会失去尾结点
        //手动将afterEnd置为空
        if (afterStart != null) {
            afterEnd.next = null;
        }

        beforeEnd.next = afterStart;//将两个链表收尾相连

        return beforeStart;//此时beforeStart是排列后链表的头结点
    }

    /*
     * NO.7
     * @ 链表的回文结构
     * */
    public boolean chkPalindrome(ListNode head) {
        //链表为空
        if (this.head == null) {
            return false;
        }

        //链表只有一个结点，一定是回文
        if (this.head.next == null) {
            return true;
        }

        //一个结点以上的情况
        //先找到中间的结点
        ListNode fast = this.head;
        ListNode slow = this.head;

        //fast每次走两步，slow走一步
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //循环结束slow指向的就是中间的节点

        //反转中间结点后面的部分
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;//当前cur指向的结点插到slow前
            slow = cur;//slow指向cur
            cur = curNext;//cur指向curNext的位置
        }

        //前面部分开始向后走，后面部分开始先前走
        while (this.head != slow) {
            //如果两个值不一样就说明不是回文返回false
            if (this.head.value != slow.value) {
                return false;
            }

            //若结点是偶数的情况
            if (this.head.next == slow) {
                return true;
            }

            //两个结点向后走
            this.head = head.next;
            slow = slow.next;

        }
        //循环结束，说明是回文，返回true
        return true;
    }

    /*
     * NO.8
     * @ 找出两个链表的公共结点
     * */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //求两个表的长度
        ListNode pl = headA;//始终指向最长的链表
        ListNode ps = headB;//始终指向最短的链表
        int lenA = 0;
        int lenB = 0;
        while (pl != null) {
            lenA++;//表A的个数加1
            pl = pl.next;//指向下一个
            //此时pl指向null
        }
        while (ps != null) {
            lenB++;//表B的个数加1
            ps = ps.next;//指向下一个
            //此时ps指向null
        }
        pl = headA;
        ps = headB;

        //求A和B的差值
        int len = lenA - lenB;//len就是
        if (len < 0) {
            //B大于A，重新将最长链表指向pl，最短指向ps
            pl = headB;
            ps = headA;
            len = lenB - lenA;//重新求差值
        }

        //最长的链表先走len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }

        //此时pl和ps指向了相同的起始位置
        //两个不相遇
        while (pl != ps) {
            pl = pl.next;//指向下一个
            ps = ps.next;//指向下一个
        }

        //如果pl为空
        if (pl == null) {
            return null;
        }

        return pl;//相交的结点
    }

    /*
    * NO.9
    * @ 判断链表是否有环
    * */
    public boolean hasCycle(ListNode head) {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null) {
            //两个结点不一样的速度在走
            fast = fast.next.next;
            slow = slow.next;
            //两个相遇说明有环
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /*
    * NO.10
    * @ 求环的入口点
    * */
    public ListNode detectCycle() {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null) {
            //两个结点不一样的速度在走
            fast = fast.next.next;
            slow = slow.next;
            //两个相遇说明有环
            if (fast == slow) {
                break;
            }
        }

        //2种情况：循环条件不满足，一种是遇到break
        if (fast == null || fast.next == null) {
            return null;//如果为空则没有环
        }

        //fast和slow此时指向相遇点
        slow = this.head;//让slow重新指向head
        while (slow != fast) {
            slow = slow.next;
            fast = fast .next;
        }
        return fast;
    }
}
    /*public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.createList();//测试创建链表1的方法
        mySingleList.disPlay();
        mySingleList.reversalList();//测试反转链表的方法
        mySingleList.disPlay();
        mySingleList.removeAllVal(234);//测试删除链表中等于给定值Val的所有结点
        mySingleList.disPlay();
        mySingleList.middleNode();//测试返回中间的结点 - 调试观看 - 当前的值是是3
        System.out.println("长度：" + mySingleList.size());//结点合数
        mySingleList.findKthToTail(2);//调试观看结果 - 结果是3

        MySingleNode mySingleNode = new MySingleNode();
        mySingleNode.createNode();//创建链表2
        mySingleNode.disPlay();//打印链表2

        //测试合并链表
        mySingleList.mergeTwoLists(mySingleList.head, mySingleList.head);

        //测试分割
        mySingleList.segmentationList(mySingleList.head, 300);
        mySingleList.disPlay();

        //测试链表回文
        mySingleList.chkPalindrome(mySingleList.head);

        //测试链表相交
        mySingleList.getIntersectionNode(mySingleList.head, mySingleList.head);
    }*/

